An LDPC (Low Density Parity Check) code has a high error correction capability and, recently, for example, has been started to be widely used for a transmission system that includes satellite digital broadcasting such as a DVB (Digital Video Broadcasting)-S.2 (for example, see Non-patent Document 1) that is employed in Europe. In addition, the LDPC code is reviewed for the employment thereof to next-generation terrestrial digital broadcasting.
According to recent researches, it can be understood, by using the LDPC code, similarly to a Turbo code or the like, a capability close to the Shannon limit can be acquired as the code length increases. In addition, since the LDPC code has a property that a minimal distance is in proportion to the code length, the LDPC has a good block error probability characteristic as its characteristic and has an advantage that a so-called error floor phenomenon, which is observed in the decoding characteristics of the Turbo code or the like, does not occur mostly.
Hereinafter, the LDPC code will be described more specifically. The LDPC code is a linear code and, here, will be described as being two dimensions, which is not necessary.
The LDPC code has a distinctive characteristic that a parity check matrix that defines the LDPC code is sparse. Here, a sparse matrix is a matrix in which the number of “1”s of elements of the matrix is very small (a matrix in which most of the elements are “0”s).
FIG. 1 illustrates an example of a parity check matrix H of an LDPC code.
In the parity check matrix H illustrated in FIG. 1, the weight (the number of “1”s) (column weight) of each column is “3”, and the weight (row weight) of each row is “6”.
In encoding (LDPC encoding) according to the LDPC code, for example, a generation matrix G is generated based on the parity check matrix H, and a code word (LDPC code) is generated by multiplying information bits of two dimensions by the generation matrix G.
More specifically, an encoding device that performs LDPC encoding, first, calculates a generation matrix G that satisfies Equation GHT=0 with HT that is a transposed matrix of the parity check matrix H. Here, in a case where the generation matrix G is a K×N matrix, the encoding device generates a code word c (=uG) formed by N bits by multiplying the generation matrix G by a bit row (vector u) of information bits formed by K bits. The code word (LDPC code) that is generated by the encoding device is received on the reception side through a predetermined communication channel.
The decoding of the LDPC code is an algorithm proposed by Gallager calling it propabilistic decoding and can be performed in accordance with a message passing algorithm that is based on belief propagation on a so-called Tanner graph that is formed by a variable node (also called a message node) and a check node. Hereinafter, the variable node and the check node will be simply referred to as nodes as is appropriate.
FIG. 2 illustrates the sequence of decoding an LDPC code.
Hereinafter, a real value (received LLR) that is acquired by representing the likelihood of “0” of the value of the i-th code bit of the LDPC code (one code word) that is received on the reception side as a log likelihood ratio will be also referred to as a received value u0i, as is appropriate. In addition, a message that is output from a check node is denoted by uj, and a message that is output from a variable node is denoted by vi.
First, in the decoding of an LDPC code, as illustrated in FIG. 2, in Step S11, the LDPC code is received, the message (check node message) uj is initialized to “0”, a variable k that takes an integer as a counter of a repetition process is initialized to “0”, and the process proceeds to Step S12. In Step S12, based on a received value u0i that is acquired by receiving the LDPC code, a message (variable node message) vi is acquired by performing a calculation (variable node calculation) represented in Equation (1), and a message uj is acquired by performing a calculation (check node calculation) represented in Equation (2) based on the message vi.
                    [                  Equation          ⁢                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢                                                          ⁢              i                                +                                    ∑                              j                =                1                                                              d                  v                                -                1                                      ⁢                          u              j                                                          (        1        )                                [                  Equation          ⁢                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, dv and dc represented in Equations (1) and (2) are parameters that represent the numbers of “1”s of the parity check matrix H in the vertical direction (column) and the horizontal direction (row), which can be arbitrarily selected, and, for example, in the case of a (3, 6) code, dv=3, and dc=6.
In addition, in the variable node calculation represented in Equation (1) and the check node calculation represented in Equation (2), each message input from a branch (edge) (a line joining the variable node and the check node) to which a message is to be output is not set as the calculation target, and accordingly, the calculation ranges are 1 to dv−1 and 1 to dc−1. The check node calculation represented in Equation (2) is actually performed by arranging a table of a function R(v1, v2) represented in Equation (3) that is defined as one output for two inputs v1 and v2 in advance and consecutively (recursively) using the table as represented in Equation (4).[Equation 3]x=2 tan h−1{tan h(v1/2)tan h(v2/2)}=R(v1,v2)  (3)[Equation 4]uj=R(v1,R(v2,R(v3, . . . R(vdo−2,vdo−1))))  (4)
Additionally, in Step S12, a variable k is incremented by one, and the process proceeds to Step S13. In Step S13, it is determined whether or not the variable k is greater than a predetermined repetition decoding number of times C. In Step S13, in a case where the variable k is determined not to be greater than C, the process is returned to Step S12, and the same process is repeated.
On the other hand, in a case where the variable k is determined to be greater than C in Step S13, the process proceeds to Step S14, a message vi as a decoding result that is finally output is acquired by performing a calculation represented in Equation (5) and is output, whereby the decoding process of the LDPC code ends.
                    [                  Equation          ⁢                                          ⁢          5                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                v                                      ⁢                          u              j                                                          (        5        )            
Here, the calculation represented in Equation (5), differently from the variable node calculation represented in Equation (1), is performed by using messages uj supplied from all the branches that are connected to the variable node.
FIG. 3 illustrates an example of the parity check matrix H of a (3, 6) LDPC code (coded rate of ½, code length of 12).
In the parity check matrix H illustrated in FIG. 3, similarly to that illustrated in FIG. 1, the weight of a column is 3, and the weight of a row is 6.
FIG. 4 illustrates a Tanner graph of the parity check matrix H illustrated in FIG. 3.
Here, in FIG. 4, a node that is denoted by a plus sign “+” is a check node, and a node that is denoted by an equal sign “=” is a variable node. The check node and the variable node correspond to a row and a column of the parity check matrix H. A line joined between a check node and a variable node is a branch (edge) and corresponds to “1” of the element of the parity check matrix.
In other words, in a case where an element of the j-th row and the i-th column of the parity check matrix is “1”, in FIG. 4, an i-th variable node (a node of “=”) from the top and a j-th check node (a node of “+”) from the top are connected through a branch. A branch represents that a code bit corresponding to the variable node has a restraint condition corresponding to the check node.
In a sum product algorithm that is a decoding method of an LDPC code, a variable node calculation and a check node calculation are repeatedly performed.
FIG. 5 illustrates a variable node calculation that is performed in a variable node.
In the variable node, a message vi that corresponds to a branch that is a calculation target is acquired by the variable node calculation that is represented in Equation (1) using messages u1 and u2 supplied from the remaining branches connected to the variable node and a received value u0i. Messages that correspond to the other branches are acquired in the same manner.
FIG. 6 illustrates a check node calculation that is performed in a check node.
Here, the check node calculation represented in Equation (2) can be rewritten into Equation (6) by using the relation of an equation of a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign(b). Here, sign(x) is 1 when x≧0, and is −1 when x<0.
                    [                  Equation          ⁢                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                                                                                                        exp                            ⁢                                                          {                                                                                                ∑                                                                      i                                    =                                    1                                                                                                                                              d                                      c                                                                        -                                    1                                                                                                  ⁢                                                                  ln                                  ⁡                                                                      (                                                                                                                                                        tanh                                        ⁡                                                                                  (                                                                                                                                    v                                              i                                                                                        2                                                                                    )                                                                                                                                                                                            )                                                                                                                              }                                                        ×                                                                                                                                                                                                          ∏                                                              i                                =                                1                                                                                                                              d                                  c                                                                -                                1                                                                                      ⁢                                                          sign                              ⁡                                                              (                                                                  tanh                                  ⁡                                                                      (                                                                                                                  v                                        i                                                                            2                                                                        )                                                                                                  )                                                                                                                                                                          ]                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                              {                                                  -                                                      (                                                                                          ∑                                                                  i                                  =                                  1                                                                                                                                      d                                    c                                                                    -                                  1                                                                                            ⁢                                                              -                                                                  ln                                  ⁡                                                                      (                                                                          tanh                                      ⁡                                                                              (                                                                                                                                                                                                                        v                                              i                                                                                                                                                                            2                                                                                )                                                                                                              )                                                                                                                                                        )                                                                          }                                                              ]                                                  ×                                                      ∏                                          i                      =                      1                                                                                      d                        c                                            -                      1                                                        ⁢                                      sign                    ⁡                                          (                                              v                        i                                            )                                                                                                                              (        6        )            
In a case where x≧0, when a function φ(x) is defined as an equation of φ(x)=ln(tan h(x/2)), an equation of φ−1(x)=2 tan h−1(e−x) is satisfied, and accordingly, Equation (6) can be transformed into Equation (7).
                    [                  Equation          ⁢                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                                              d                      c                                        -                    1                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ×                                    ∏                              i                =                1                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
In a check node, the check node calculation represented in Equation (2) is performed based on Equation (7).
In other words, in a check node, as illustrated in FIG. 6, a message uj that corresponds to a branch that is a calculation target can be acquired through the check node calculation represented in Equation (7) using messages v1, v2, v3, v4, and v5 supplied from the remaining branches connected to the check node. Messages corresponding to the other branches are acquired in the same manner.
In addition, the function φ(x) represented in Equation (7) can be represented as an equation of φ(x)=ln((ex+1)/(ex−1)), and φ(x)=φ−1(x) for x>0. In order to implement the functions φ(x) and φ−1(x) in hardware, there are cases where the functions are implemented using LUTs (Look Up Tables), and the LUTs are the same for both the functions.